home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / gif.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  13KB  |  485 lines
  1. /* 
  2.  *    gif -
  3.  *         Based on GIFENCOD by David Rowley 
  4.  *    <mgardi@watdscu.waterloo.edu>.  With Lempel-Zim compression based 
  5.  *    on "compress".
  6.  *
  7.  * GIFENCODE.C    - GIF Image compression interface
  8.  *
  9.  * GIFEncode( FName, GHeight, GWidth, GInterlace, Background,
  10.  *            BitsPerPixel, Red, Green, Blue, GetPixel )
  11.  *
  12.  */
  13. #include "stdio.h"
  14. #include "ctype.h"
  15.  
  16. typedef int (* ifunptr)();
  17.  
  18. static int Width, Height;
  19. static int curx, cury;
  20. static long CountDown;
  21. static int Pass;
  22. static int Interlace;
  23. static unsigned long cur_accum = 0;
  24. static int cur_bits = 0;
  25.  
  26. /*
  27.  * Bump the 'curx' and 'cury' to point to the next pixel
  28.  */
  29. static BumpPixel()
  30. {
  31.     curx++;
  32.     if( curx == Width ) {
  33.     curx = 0;
  34.     if( !Interlace ) {
  35.         cury++;
  36.     } else {
  37.         switch( Pass ) {
  38.              case 0:
  39.             cury += 8;
  40.             if( cury >= Height ) {
  41.             Pass++;
  42.             cury = 4;
  43.             } 
  44.             break;
  45.         case 1:
  46.             cury += 8;
  47.                 if( cury >= Height ) {
  48.                 Pass++;
  49.                 cury = 2;
  50.                   }
  51.                   break;
  52.                case 2:
  53.             cury += 4;
  54.             if( cury >= Height ) {
  55.                  Pass++;
  56.             cury = 1;
  57.             }
  58.             break;
  59.                case 3:
  60.             cury += 2;
  61.             break;
  62.         }
  63.     }
  64.     }
  65. }
  66.  
  67. /*
  68.  * Return the next pixel from the image
  69.  */
  70. static GIFNextPixel( getpixel )
  71. ifunptr getpixel;
  72. {
  73.     int r;
  74.  
  75.     if( CountDown == 0 )
  76.     return EOF;
  77.     CountDown--;
  78.     r = (*getpixel)( curx, cury );
  79.     BumpPixel();
  80.     return r;
  81. }
  82.  
  83. /*
  84.  * Write out a word to the GIF file
  85.  */
  86. static Putword( w, fp )
  87. int w;
  88. FILE *fp;
  89. {
  90.     fputc( w & 0xff, fp );
  91.     fputc( (w/256) & 0xff, fp );
  92. }
  93.  
  94. /***************************************************************************
  95.  *
  96.  *  GIFCOMPR.C       - GIF Image compression routines
  97.  *
  98.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  99.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  100.  *
  101.  ***************************************************************************/
  102.  
  103. #define CBITS    12
  104. #define HSIZE  5003            /* 80% occupancy */
  105.  
  106. /*
  107.  * a code_int must be able to hold 2**CBITS values of type int, and also -1
  108.  */
  109. typedef int             code_int;
  110. typedef long int        count_int;
  111. typedef unsigned char      char_type;
  112.  
  113. /*
  114.  *
  115.  * GIF Image compression - modified 'compress'
  116.  *
  117.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  118.  *
  119.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  120.  *              Jim McKie               (decvax!mcvax!jim)
  121.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  122.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  123.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  124.  *              Joe Orost               (decvax!vax135!petsd!joe)
  125.  *
  126.  */
  127.  
  128. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  129.  
  130. static int n_bits;                        /* number of bits/code */
  131. static int maxbits = CBITS;                /* user settable max # bits/code */
  132. static code_int maxcode;                  /* maximum code, given n_bits */
  133. static code_int maxmaxcode = (code_int)1 << CBITS; /* should NEVER generate this code */
  134. # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
  135.  
  136. static count_int htab [HSIZE];
  137. static unsigned short codetab [HSIZE];
  138. #define HashTabOf(i)       htab[i]
  139. #define CodeTabOf(i)    codetab[i]
  140.  
  141. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  142.  
  143. /*
  144.  * To save much memory, we overlay the table used by gifcompress() with those
  145.  * used by decompress().  The tab_prefix table is the same size and type
  146.  * as the codetab.  The tab_suffix table needs 2**CBITS characters.  We
  147.  * get this from the beginning of htab.  The output stack uses the rest
  148.  * of htab, and contains characters.  There is plenty of room for any
  149.  * possible stack (stack used to be 8000 characters).
  150.  */
  151. #define tab_prefixof(i) CodeTabOf(i)
  152. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  153. #define de_stack               ((char_type *)&tab_suffixof((code_int)1<<CBITS))
  154.  
  155. static code_int free_ent = 0;                  /* first unused entry */
  156.  
  157. /*
  158.  * block compression parameters -- after all codes are used up,
  159.  * and compression rate changes, start over.
  160.  */
  161. static int clear_flg = 0;
  162. static int offset;
  163. static long int in_count = 1;            /* length of input */
  164. static long int out_count = 0;           /* # of codes output (for debugging) */
  165. static int g_init_bits;
  166. static FILE *g_outfile;
  167. static int ClearCode;
  168. static int EOFCode;
  169. static char accum[256];
  170. static unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  171.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  172.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  173.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  174.  
  175. /*
  176.  * Number of characters so far in this 'packet'
  177.  */
  178. static int a_count;
  179.  
  180. /*
  181.  * Set up the 'byte output' routine
  182.  */
  183. static char_init()
  184. {
  185.         a_count = 0;
  186. }
  187.  
  188. /*
  189.  * Flush the packet to disk, and reset the accumulator
  190.  */
  191. static flush_char()
  192. {
  193.         if( a_count > 0 ) {
  194.                 fputc( a_count, g_outfile );
  195.                 fwrite( accum, 1, a_count, g_outfile );
  196.                 a_count = 0;
  197.         }
  198. }
  199.  
  200. /*
  201.  * Add a character to the end of the current packet, and if it is 254
  202.  * characters, flush the packet to disk.
  203.  */
  204. static char_out( c )
  205. int c;
  206. {
  207.         accum[ a_count++ ] = c;
  208.         if( a_count >= 254 )
  209.                 flush_char();
  210. }
  211.  
  212. static writeerr()
  213. {
  214.         printf( "error writing GIF file\n" );
  215.         exit(1);
  216. }
  217.  
  218. /*****************************************************************
  219.  * TAG( output )
  220.  *
  221.  * Output the given code.
  222.  * Inputs:
  223.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  224.  *              that n_bits =< (long)wordsize - 1.
  225.  * Outputs:
  226.  *      Outputs code to the file.
  227.  * Assumptions:
  228.  *      Chars are 8 bits long.
  229.  * Algorithm:
  230.  *      Maintain a CBITS character long buffer (so that 8 codes will
  231.  * fit in it exactly).  Use the VAX insv instruction to insert each
  232.  * code in turn.  When the buffer fills up empty it and start over.
  233.  */
  234. static output( code )
  235. code_int  code;
  236. {
  237.     cur_accum &= masks[ cur_bits ];
  238.     if( cur_bits > 0 )
  239.         cur_accum |= ((long)code << cur_bits);
  240.     else
  241.         cur_accum = code;
  242.     cur_bits += n_bits;
  243.     while( cur_bits >= 8 ) {
  244.         char_out( (unsigned int)(cur_accum & 0xff) );
  245.         cur_accum >>= 8;
  246.         cur_bits -= 8;
  247.     }
  248.  
  249.     /*
  250.      * If the next entry is going to be too big for the code size,
  251.      * then increase it, if possible.
  252.      */
  253.    if ( free_ent > maxcode || clear_flg ) {
  254.             if( clear_flg ) {
  255.                 maxcode = MAXCODE (n_bits = g_init_bits);
  256.                 clear_flg = 0;
  257.             } else {
  258.                 n_bits++;
  259.                 if ( n_bits == maxbits )
  260.                     maxcode = maxmaxcode;
  261.                 else
  262.                     maxcode = MAXCODE(n_bits);
  263.             }
  264.     }
  265.     if( code == EOFCode ) {
  266.         /*
  267.          * At EOF, write the rest of the buffer.
  268.          */
  269.         while( cur_bits > 0 ) {
  270.                 char_out( (unsigned int)(cur_accum & 0xff) );
  271.                 cur_accum >>= 8;
  272.                 cur_bits -= 8;
  273.         }
  274.         flush_char();
  275.         fflush( g_outfile );
  276.         if( ferror( g_outfile ) )
  277.                 writeerr();
  278.     }
  279. }
  280.  
  281.  
  282. /*
  283.  * Clear out the hash table
  284.  */
  285. static cl_hash(hsize)          /* reset code table */
  286. count_int hsize;
  287. {
  288.         count_int *htab_p = htab+hsize;
  289.         long i;
  290.         long m1 = -1;
  291.  
  292.         i = hsize - 16;
  293.         do {                            /* might use Sys V memset(3) here */
  294.                 *(htab_p-16) = m1;
  295.                 *(htab_p-15) = m1;
  296.                 *(htab_p-14) = m1;
  297.                 *(htab_p-13) = m1;
  298.                 *(htab_p-12) = m1;
  299.                 *(htab_p-11) = m1;
  300.                 *(htab_p-10) = m1;
  301.                 *(htab_p-9) = m1;
  302.                 *(htab_p-8) = m1;
  303.                 *(htab_p-7) = m1;
  304.                 *(htab_p-6) = m1;
  305.                 *(htab_p-5) = m1;
  306.                 *(htab_p-4) = m1;
  307.                 *(htab_p-3) = m1;
  308.                 *(htab_p-2) = m1;
  309.                 *(htab_p-1) = m1;
  310.                 htab_p -= 16;
  311.         } while ((i -= 16) >= 0);
  312.         for ( i += 16; i > 0; i-- )
  313.                 *--htab_p = m1;
  314. }
  315.  
  316. static cl_block ()             /* table clear for block compress */
  317. {
  318.         cl_hash ( (count_int) hsize );
  319.         free_ent = ClearCode + 2;
  320.         clear_flg = 1;
  321.         output( (code_int)ClearCode );
  322. }
  323.  
  324. /*
  325.  * compress stdin to stdout
  326.  *
  327.  * Algorithm:  use open addressing double hashing (no chaining) on the
  328.  * prefix code / next character combination.  We do a variant of Knuth's
  329.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  330.  * secondary probe.  Here, the modular division first probe is gives way
  331.  * to a faster exclusive-or manipulation.  Also do block compression with
  332.  * an adaptive reset, whereby the code table is cleared when the compression
  333.  * ratio decreases, but after the table fills.  The variable-length output
  334.  * codes are re-sized at this point, and a special CLEAR code is generated
  335.  * for the decompressor.  Late addition:  construct the table according to
  336.  * file size for noticeable speed improvement on small files.  Please direct
  337.  * questions about this implementation to ames!jaw.
  338.  */
  339. static gifcompress( init_bits, outfile, ReadValue )
  340. int init_bits;
  341. FILE *outfile;
  342. ifunptr ReadValue;
  343. {
  344.     long fcode;
  345.     code_int i = 0;
  346.     int c;
  347.     code_int ent;
  348.     code_int disp;
  349.     code_int hsize_reg;
  350.     int hshift;
  351.  
  352.     /*
  353.      * Set up the globals:  g_init_bits - initial number of bits
  354.      *                      g_outfile   - pointer to output file
  355.      */
  356.     g_init_bits = init_bits;
  357.     g_outfile = outfile;
  358.     /*
  359.      * Set up the necessary values
  360.      */
  361.     offset = 0;
  362.     out_count = 0;
  363.     clear_flg = 0;
  364.     in_count = 1;
  365.     maxcode = MAXCODE(n_bits = g_init_bits);
  366.     ClearCode = (1 << (init_bits - 1));
  367.     EOFCode = ClearCode + 1;
  368.     free_ent = ClearCode + 2;
  369.     char_init();
  370.     ent = GIFNextPixel( ReadValue );
  371.     hshift = 0;
  372.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  373.         hshift++;
  374.     hshift = 8 - hshift;                /* set hash code range bound */
  375.     hsize_reg = hsize;
  376.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  377.     output( (code_int)ClearCode );
  378.     while ( (c = GIFNextPixel( ReadValue )) != EOF ) {
  379.         in_count++;
  380.         fcode = (long) (((long) c << maxbits) + ent);
  381.         /* i = (((code_int)c << hshift) ~ ent);    /* xor hashing */
  382.         i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  383.         if ( HashTabOf (i) == fcode ) {
  384.             ent = CodeTabOf (i);
  385.             continue;
  386.         } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  387.             goto nomatch;
  388.         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  389.         if ( i == 0 )
  390.             disp = 1;
  391. probe:
  392.         if ( (i -= disp) < 0 )
  393.             i += hsize_reg;
  394.         if ( HashTabOf (i) == fcode ) {
  395.             ent = CodeTabOf (i);
  396.             continue;
  397.         }
  398.         if ( (long)HashTabOf (i) > 0 )
  399.             goto probe;
  400. nomatch:
  401.         output ( (code_int) ent );
  402.         out_count++;
  403.         ent = c;
  404.         if ( free_ent < maxmaxcode ) {
  405.             CodeTabOf (i) = free_ent++; /* code -> hashtable */
  406.             HashTabOf (i) = fcode;
  407.         } else
  408.                 cl_block();
  409.     }
  410.     /*
  411.      * Put out the final code.
  412.      */
  413.     output( (code_int)ent );
  414.     out_count++;
  415.     output( (code_int) EOFCode );
  416.     return;
  417. }
  418.  
  419. /*
  420.  * public GIFEncode
  421.  */
  422. GIFEncode( fp, GWidth, GHeight, GInterlace, Background,
  423.            BitsPerPixel, Red, Green, Blue, GetPixel )
  424. FILE *fp;
  425. int GWidth, GHeight;
  426. int GInterlace;
  427. int Background;
  428. int BitsPerPixel;
  429. unsigned char Red[], Green[], Blue[];
  430. ifunptr GetPixel;
  431. {
  432.     int B;
  433.     int RWidth, RHeight;
  434.     int LeftOfs, TopOfs;
  435.     int Resolution;
  436.     int ColorMapSize;
  437.     int InitCodeSize;
  438.     int i;
  439.  
  440.     long cur_accum = 0;
  441.     cur_bits = 0;
  442.  
  443.     Interlace = GInterlace;
  444.     ColorMapSize = 1 << BitsPerPixel;
  445.     RWidth = Width = GWidth;
  446.     RHeight = Height = GHeight;
  447.     LeftOfs = TopOfs = 0;
  448.     Resolution = BitsPerPixel;
  449.  
  450.     CountDown = (long)Width * (long)Height;
  451.     Pass = 0;
  452.     if( BitsPerPixel <= 1 )
  453.     InitCodeSize = 2;
  454.     else
  455.     InitCodeSize = BitsPerPixel;
  456.     curx = cury = 0;
  457.     fwrite( "GIF87a", 1, 6, fp );
  458.     Putword( RWidth, fp );
  459.     Putword( RHeight, fp );
  460.     B = 0x80;       /* Yes, there is a color map */
  461.     B |= (Resolution - 1) << 5;
  462.     B |= (BitsPerPixel - 1);
  463.     fputc( B, fp );
  464.     fputc( Background, fp );
  465.     fputc( 0, fp );
  466.     for( i=0; i<ColorMapSize; i++ ) {
  467.     fputc( Red[i], fp );
  468.     fputc( Green[i], fp );
  469.     fputc( Blue[i], fp );
  470.     }
  471.     fputc( ',', fp );
  472.     Putword( LeftOfs, fp );
  473.     Putword( TopOfs, fp );
  474.     Putword( Width, fp );
  475.     Putword( Height, fp );
  476.     if( Interlace )
  477.     fputc( 0x40, fp );
  478.     else
  479.     fputc( 0x00, fp );
  480.     fputc( InitCodeSize, fp );
  481.     gifcompress( InitCodeSize+1, fp, GetPixel );
  482.     fputc( 0, fp );
  483.     fputc( ';', fp );
  484. }
  485.